import java.util.Arrays;

/*
* Алгоритм Бойера—Мура
*/
final public class PatternSearch {

    final WordIndex patword;
    final byte[] pattern;
    final private int patlen;
    final private int[] offset; // символы win1251
    final private int[] suffix;

    PatternSearch(final WordIndex pattern_text) {
        patword = pattern_text;
        pattern = pattern_text.value;
        patlen = pattern_text.length();
        offset = new int[256];
        suffix = new int[patlen + 1];
        createOffset();
        createSuffix();
    }

    /*
     * Вспомогательные методы для indexOf.
     * Построение маски паттерна для алгоритма Бойера—Мура
     */
    private void createOffset() {
        Arrays.fill(offset, patlen); // заполняем базовыми значениями
        for (int i = 0; i < patlen; i++) {
            offset[(int) pattern[i] & 0xFF] = i; // byte в беззнаковое целое
            offset[(int) Word.reverseCase(pattern[i]) & 0xFF] = i;
        }
    }

    private void createSuffix() {
        Arrays.fill(suffix, patlen);
        suffix[patlen] = 1;
        for (int i = patlen - 1; i >= 0; i--) {
            for (int at = i; at < patlen; at++) {
                final byte[] s = Word.substring(pattern, at, patlen); // с какого символа берем подстроку
                for (int j = at - 1; j >= 0; j--) {
                    final byte[] p = Word.substring(pattern, j, j + s.length); // берем подстроку той же длинны
                    if (Word.equalsNoCase(p, s)) {
                        suffix[i] = at - 1;
                        at = patlen;
                        break;
                    }
                }
            }
        }
    }

    /**
     * Возвращает индекс, под которым шаблон (this.pattern) первый раз появляется в строке
     * Поиск выполняется без учета регистра
     * @param textvalue - строка, где искать шаблон
     * @return возвращает (-1) если символ или строка не найдены.
     */
    public int index(final byte[] textvalue) {
        int t = 0;
        final int last = patlen - 1;
        final int textlen = textvalue.length;
        while (t < textlen - last) {
            int p = last;
            while (p >= 0 && Word.equalsNoCase(textvalue[t + p], pattern[p])) {
                p--;
            }
            if (p == -1) {
                return t;
            }
            t += Math.max(p - offset[(int) textvalue[t + p] & 0xFF], suffix[p + 1]); // byte в беззнаковое
        }
        return -1;
    }
}